{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Safest Path in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #union-find #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #并查集 #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSafenessFactor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出最安全路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、大小为 <code>n x n</code> 的二维矩阵 <code>grid</code> ，其中 <code>(r, c)</code> 表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>grid[r][c] = 1</code> ，则表示一个存在小偷的单元格</li>\n",
    "\t<li>如果 <code>grid[r][c] = 0</code> ，则表示一个空单元格</li>\n",
    "</ul>\n",
    "\n",
    "<p>你最开始位于单元格 <code>(0, 0)</code> 。在一步移动中，你可以移动到矩阵中的任一相邻单元格，包括存在小偷的单元格。</p>\n",
    "\n",
    "<p>矩阵中路径的 <strong>安全系数</strong> 定义为：从路径中任一单元格到矩阵中任一小偷所在单元格的 <strong>最小</strong> 曼哈顿距离。</p>\n",
    "\n",
    "<p>返回所有通向单元格<em> </em><code>(n - 1, n - 1)</code> 的路径中的 <strong>最大安全系数</strong> 。</p>\n",
    "\n",
    "<p>单元格 <code>(r, c)</code> 的某个 <strong>相邻</strong> 单元格，是指在矩阵中存在的 <code>(r, c + 1)</code>、<code>(r, c - 1)</code>、<code>(r + 1, c)</code> 和 <code>(r - 1, c)</code> 之一。</p>\n",
    "\n",
    "<p>两个单元格 <code>(a, b)</code> 和 <code>(x, y)</code> 之间的 <strong>曼哈顿距离</strong> 等于 <code>| a - x | + | b - y |</code> ，其中 <code>|val|</code> 表示 <code>val</code> 的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/02/example1.png\" style=\"width: 362px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0],[0,0,0],[0,0,1]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/02/example2.png\" style=\"width: 362px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,1],[0,0,0],[0,0,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "上图所示路径的安全系数为 2：\n",
    "- 该路径上距离小偷所在单元格（0，2）最近的单元格是（0，0）。它们之间的曼哈顿距离为 | 0 - 0 | + | 0 - 2 | = 2 。\n",
    "可以证明，不存在安全系数更高的其他路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/02/example3.png\" style=\"width: 362px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "上图所示路径的安全系数为 2：\n",
    "- 该路径上距离小偷所在单元格（0，3）最近的单元格是（1，2）。它们之间的曼哈顿距离为 | 0 - 1 | + | 3 - 2 | = 2 。\n",
    "- 该路径上距离小偷所在单元格（3，0）最近的单元格是（3，2）。它们之间的曼哈顿距离为 | 3 - 3 | + | 0 - 2 | = 2 。\n",
    "可以证明，不存在安全系数更高的其他路径。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grid.length == n &lt;= 400</code></li>\n",
    "\t<li><code>grid[i].length == n</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>grid</code> 至少存在一个小偷</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-safest-path-in-a-grid](https://leetcode.cn/problems/find-the-safest-path-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-safest-path-in-a-grid](https://leetcode.cn/problems/find-the-safest-path-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0],[0,0,0],[0,0,1]]', '[[0,0,1],[0,0,0],[0,0,0]]', '[[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append([i, j, 1])\n",
    "        \n",
    "        while q:\n",
    "            i, j, stp = q.popleft()\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if m > x >= 0 <= y < n and grid[x][y] == 0:\n",
    "                    q.append((x, y, stp + 1))\n",
    "                    grid[x][y] = stp + 1\n",
    "\n",
    "        h = [(-grid[0][0], 0, 0)]\n",
    "        while h:\n",
    "            dis, i, j = heappop(h)\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if not (m > x >= 0 <= y < n) or grid[x][y] == -1: continue\n",
    "                if x == n - 1 and y == m - 1:\n",
    "                    return min(-dis, grid[x][y]) - 1\n",
    "                heappush(h, (max(dis, -grid[x][y]), x, y))\n",
    "                grid[x][y] = -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dq = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dq.append((i, j))\n",
    "        while dq:\n",
    "            a, b = dq.popleft()\n",
    "            d = grid[a][b]\n",
    "            for x, y in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                    grid[x][y] = d + 1\n",
    "                    dq.append((x, y))\n",
    "        \n",
    "        \n",
    "        left, right = 1, min(grid[0][0], grid[-1][-1])\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            vis = [[False] * n for _ in range(n)]\n",
    "            \n",
    "            dq.append((0, 0))\n",
    "            vis[0][0] = True\n",
    "            while dq:\n",
    "                a, b = dq.popleft()\n",
    "                if (a, b) == (n-1, n-1):\n",
    "                    dq.clear()\n",
    "                    break\n",
    "                for x, y in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                    if 0 <= x < n and 0 <= y < n and not vis[x][y]:\n",
    "                        vis[x][y] = True\n",
    "                        if grid[x][y] >= mid:\n",
    "                            dq.append((x, y))\n",
    "            if vis[-1][-1]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, -1, 0, 1]\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append([i, j])\n",
    "                    dis[i][j] = 0\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0 and dis[nx][ny] == -1:\n",
    "                     dis[nx][ny] = dis[x][y] + 1\n",
    "                     q.append([nx, ny])\n",
    "        # 大根堆\n",
    "        h = []\n",
    "        ans = dis[0][0]\n",
    "        vis = [[False] * n for _ in range(n)]\n",
    "        heappush(h, [-dis[0][0], 0, 0])\n",
    "        while h:\n",
    "            d, x, y = heappop(h)\n",
    "            if vis[x][y]:\n",
    "                continue\n",
    "            vis[x][y] = True\n",
    "            if x == n - 1 and y == n - 1:\n",
    "                return -d\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if 0 <= nx < n and 0 <= ny < n and not vis[nx][ny]:\n",
    "                    heappush(h, [-min(-d, dis[nx][ny]), nx, ny])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        mp = [[0x900 for i in range(n)] for j in range(n)]\n",
    "        step = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        que = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    mp[i][j] = 0\n",
    "                    que.append([i, j])\n",
    "        while que:\n",
    "            x, y = que.popleft()\n",
    "            for i in step:\n",
    "                tx, ty = x + i[0], y + i[1]\n",
    "                if -1 < tx < n and -1 < ty < n and mp[tx][ty] > mp[x][y] + 1:\n",
    "                    que.append([tx, ty])\n",
    "                    mp[tx][ty] = mp[x][y] + 1\n",
    "        tgt = mp[0][0]\n",
    "        rec = [[1 for i in range(n)] for j in range(n)]\n",
    "        rec[0][0] = 0\n",
    "        nextque = collections.deque()\n",
    "        while True:\n",
    "            que = nextque\n",
    "            que.append([0, 0])\n",
    "            nextque = collections.deque()\n",
    "            while que:\n",
    "                x, y = que.popleft()\n",
    "                for i in step:\n",
    "                    tx, ty = x + i[0], y + i[1]\n",
    "                    if -1 < tx < n and -1 < ty < n and rec[tx][ty]:\n",
    "                        if mp[tx][ty] > tgt:\n",
    "                            que.append([tx, ty])\n",
    "                            rec[tx][ty] = 0\n",
    "                        elif mp[tx][ty] == tgt:\n",
    "                            que.append([tx, ty])\n",
    "                            nextque.append([tx, ty])\n",
    "                            rec[tx][ty] = 0\n",
    "            if rec[-1][-1] == 0:\n",
    "                return tgt\n",
    "            else:\n",
    "                tgt = tgt - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind(object):\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1: return 0\n",
    "        dis = [[inf for i in range(n)] for j in range(n)]\n",
    "        #multi-source BFS\n",
    "        monsters = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dis[i][j] = 0\n",
    "                    monsters.append((i,j))\n",
    "        destinations = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        while monsters:\n",
    "            x, y = monsters.popleft()\n",
    "            for dx,dy in destinations:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n and dis[nx][ny] == inf:\n",
    "                    dis[nx][ny] = dis[x][y] + 1\n",
    "                    monsters.append((nx, ny))\n",
    "        def check(k):\n",
    "            unionf = UnionFind(n*n)\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if dis[x][y] >= k:\n",
    "                        for dx,dy in ((0,1), (1,0)):\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < n and 0 <= ny < n and dis[nx][ny] >= k:\n",
    "                                unionf.union(x*n+y,nx*n+ny)\n",
    "            return unionf.connected(0, n*n-1)\n",
    "        l,r = 0, 2*n\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l  = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "    def find(self, a):\n",
    "        a = self.parent[a]\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        pa, pb = self.find(a), self.find(b)\n",
    "        if pa == pb: return False\n",
    "        self.parent[pb] = pa\n",
    "        return True\n",
    "\n",
    "    def same(self, a, b):\n",
    "        return self.find(a) == self.find(b)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, g: List[List[int]]) -> int:\n",
    "        n = len(g)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        dist = [[inf]*n for _ in range(n)]\n",
    "        q = deque([(i, j) for i in range(n) for j in range(n) if g[i][j] == 1])\n",
    "        for i, j in q:\n",
    "            dist[i][j] = 0\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for di, dj in pairwise([-1, 0, 1, 0, -1]):\n",
    "                ni, nj = i+di, j+dj \n",
    "                if ni < 0 or ni >= n or nj < 0 or nj >= n:\n",
    "                    continue\n",
    "                if dist[ni][nj] != inf:\n",
    "                    continue\n",
    "                dist[ni][nj] = dist[i][j]+1\n",
    "                q.append((ni, nj))\n",
    "\n",
    "        ac, wa = 0, 800\n",
    "        while abs(ac-wa) > 1:\n",
    "            wj = (ac+wa)//2\n",
    "\n",
    "            uf = UnionFind(n*n)\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if dist[i][j] >= wj:\n",
    "                        if i+1 < n and dist[i+1][j] >= wj:\n",
    "                            uf.merge(i*n+j, (i+1)*n+j)\n",
    "                        if j+1 < n and dist[i][j+1] >= wj:\n",
    "                            uf.merge(i*n+j, i*n+j+1)\n",
    "            \n",
    "            if uf.same(0, n*n-1):\n",
    "                ac = wj \n",
    "            else:\n",
    "                wa = wj \n",
    "        return ac"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        if grid[0][0]==1 or grid[-1][-1]==1: return 0\n",
    "        ones=deque()\n",
    "        dis=[[-1]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dis[i][j]=0\n",
    "                    ones.append((i,j))\n",
    "        while ones:\n",
    "            i,j=ones.popleft()\n",
    "            for x, y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                if 0<=x<n and 0<=y<n and dis[x][y]<0:\n",
    "                    dis[x][y]=dis[i][j]+1\n",
    "                    ones.append((x,y))\n",
    "        #print(dis)\n",
    "        '''@lru_cache(None)\n",
    "        def dfs(i,j,f):\n",
    "            #print(i,j,f)\n",
    "            if i<0 or i>=n or j<0 or j>=n: return -inf\n",
    "            m=min(dis[i][j],f)\n",
    "            if i==n-1 and j==n-1: return m\n",
    "            if grid[i][j]==-1:return -inf\n",
    "            tmp=grid[i][j]\n",
    "            grid[i][j]=-1\n",
    "            s=0\n",
    "            for x, y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                s=max(s,dfs(x,y,m))\n",
    "            #s=dfs(min,m)\n",
    "            grid[i][j]=tmp\n",
    "            return s\n",
    "        return dfs(0,0,inf)'''\n",
    "\n",
    "        q=[(-dis[0][0],0,0)]\n",
    "        m=inf\n",
    "        v=set()\n",
    "        #v.add((i,j))\n",
    "        while q:\n",
    "            #print(q)\n",
    "            f,i,j=heappop(q)\n",
    "            #print(f,i,j)\n",
    "            if (i,j) in v: continue\n",
    "            v.add((i,j))\n",
    "            m=min(m,-f)\n",
    "            if i==n-1 and j==n-1:\n",
    "                return m\n",
    "            for x, y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                if 0<=x<n and 0<=y<n:\n",
    "                    heappush(q,(-dis[x][y],x,y))\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "\n",
    "        def check(high):\n",
    "            if grid[0][0] < high or grid[-1][-1] < high: return 0\n",
    "            q = [(0, 0)]\n",
    "            visited = set(q)\n",
    "            while q:\n",
    "                tmp, q = q, []\n",
    "                for i, j in tmp:\n",
    "                    if (i, j) == END: return 1\n",
    "                    for di, dj in DIRS:\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in visited and grid[ni][nj] >= high:\n",
    "                            visited.add((ni, nj))\n",
    "                            q.append((ni, nj))\n",
    "            return 0\n",
    "        \n",
    "        n = len(grid)\n",
    "        q = []\n",
    "        END = (n - 1, n - 1)\n",
    "        DIRS = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i, j))\n",
    "                    grid[i][j] = 0\n",
    "                else:\n",
    "                    grid[i][j] = -1\n",
    "\n",
    "        d = 0\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            d += 1\n",
    "            for i, j in tmp:\n",
    "                for di, dj in DIRS:\n",
    "                    ni, nj = i + di, j + dj\n",
    "                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == -1:\n",
    "                        grid[ni][nj] = d\n",
    "                        q.append((ni, nj))\n",
    "        return d - bisect_left(range(d, -1, -1), 1, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append([i, j, 1])\n",
    "        \n",
    "        while q:\n",
    "            i, j, stp = q.popleft()\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if m > x >= 0 <= y < n and grid[x][y] == 0:\n",
    "                    q.append((x, y, stp + 1))\n",
    "                    grid[x][y] = stp + 1\n",
    "        print(grid)\n",
    "        h = [(-grid[0][0], 0, 0)]\n",
    "        while h:\n",
    "            dis, i, j = heappop(h)\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if not (m > x >= 0 <= y < n): continue\n",
    "                if x == n - 1 and y == m - 1:\n",
    "                    return min(-dis, grid[x][y]) - 1\n",
    "                heappush(h, (max(dis, -grid[x][y]), x, y))\n",
    "                grid[x][y] = -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet():\n",
    "    # 并查集\n",
    "    def __init__(self,n):\n",
    "        self.father = [i for i in range(n)]\n",
    "    def find(self, x):\n",
    "        if x!=self.father[x]:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    def merge(self, x, y):\n",
    "        px = self.find(x)\n",
    "        py = self.find(y)\n",
    "        if px!=py:\n",
    "            self.father[px] = py\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = list()\n",
    "        dis = [[-1]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    q.append((i, j))\n",
    "                    dis[i][j] = 0\n",
    "        # 多源bfs\n",
    "        groups = [q]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for (i, j) in tmp:\n",
    "                for ni, nj in [(i+1, j), (i-1,j), (i, j+1), (i, j-1)]:\n",
    "                    if 0<=ni<n and 0<=nj<n and dis[ni][nj]==-1:\n",
    "                        dis[ni][nj] = len(groups)\n",
    "                        q.append((ni, nj))\n",
    "            if q:\n",
    "                groups.append(q)\n",
    "\n",
    "        # 并查集判断是否相通\n",
    "        union_set = UnionSet(n*n)\n",
    "        for d in range(len(groups)-1, 0, -1):\n",
    "            for i, j in groups[d]:\n",
    "                for ni, nj in [(i+1, j), (i-1,j), (i, j+1), (i, j-1)]:\n",
    "                    if 0<=ni<n and 0<=nj<n and dis[ni][nj]>=d:\n",
    "                        union_set.merge(i*n+j, ni*n+nj)\n",
    "                       \n",
    "            if union_set.find(0)==union_set.find(n*n-1):\n",
    "                return d \n",
    "        \n",
    "        return 0\n",
    "                         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = [[-1]*n for _ in range(n)]\n",
    "        group = []\n",
    "        q = []\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    q.append([i,j])\n",
    "                    dist[i][j] = 0\n",
    "        \n",
    "        group.append(q)\n",
    "        while q:\n",
    "            temp = q[:]\n",
    "            q = []\n",
    "            for x, y in temp:\n",
    "                for nx, ny in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                    if 0<=nx<n and 0<=ny<n and dist[nx][ny]<0:\n",
    "                        dist[nx][ny] = len(group)\n",
    "                        q.append([nx, ny])\n",
    "            group.append(q)\n",
    "        \n",
    "        fa = list(range(n*n))\n",
    "        def find(a):\n",
    "            x = a\n",
    "            while fa[x] != x:\n",
    "                x = fa[x]\n",
    "            fa[a] = x\n",
    "            return x\n",
    "        def union(a, b):\n",
    "            fa[find(a)] = find(b)\n",
    "        \n",
    "        for d in range(len(group)-2, -1, -1):\n",
    "            for x, y in group[d]:\n",
    "                for nx, ny in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                    if 0<=nx<n and 0<=ny<n and dist[nx][ny]>=dist[x][y]:\n",
    "                        union(x*n+y, nx*n+ny)\n",
    "            if find(0)==find((n-1)*n+n-1):\n",
    "                return d\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        s = set()\n",
    "        hi = inf\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    s.add((i, j))\n",
    "                    hi = min(hi, i + j)\n",
    "                    hi = min(hi, n - 1 - i + n - 1 - j)\n",
    "\n",
    "        dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        def getAll(val):  # 找到所有到小偷距离小于 val 的点\n",
    "            if val < 0: return set()\n",
    "            dq = deque(x for x in s)\n",
    "            res = set(x for x in s)\n",
    "            step = 0\n",
    "            while dq:\n",
    "                dq2 = deque()\n",
    "                step += 1\n",
    "                if step >= val:\n",
    "                    break\n",
    "                while dq:\n",
    "                    x, y = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        u, v = x + dx, y + dy\n",
    "                        if 0 <= u < n and 0 <= v < n and (u, v) not in res:\n",
    "                            dq2.append((u, v))\n",
    "                            res.add((u, v))\n",
    "                dq = dq2\n",
    "            return res\n",
    "\n",
    "        def check(val):\n",
    "            vis = getAll(val)\n",
    "            if (0, 0) in vis:\n",
    "                return False\n",
    "\n",
    "            dq = deque([(0, 0)])\n",
    "            vis.add((0, 0))\n",
    "            while dq:\n",
    "                x, y = dq.popleft()\n",
    "                for dx, dy in dir:\n",
    "                    u, v = x + dx, y + dy\n",
    "                    if 0 <= u < n and 0 <= v < n and (u, v) not in vis:\n",
    "                        if u == v == n - 1:\n",
    "                            return True\n",
    "                        dq.append((u, v))\n",
    "                        vis.add((u, v))\n",
    "            return False\n",
    "        lo, hi = 0, hi + 1\n",
    "        while lo < hi - 1:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = []\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    q.append((i, j))\n",
    "                    dis[i][j] = 0\n",
    "\n",
    "        groups = [q]\n",
    "        while q:  # 多源 BFS\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < n and 0 <= y < n and dis[x][y] < 0:\n",
    "                        q.append((x, y))\n",
    "                        dis[x][y] = len(groups)\n",
    "            groups.append(q)  # 相同 dis 分组记录\n",
    "\n",
    "        # 并查集模板\n",
    "        fa = list(range(n * n))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for d in range(len(groups) - 2, 0, -1):\n",
    "            for i, j in groups[d]:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < n and 0 <= y < n and dis[x][y] >= dis[i][j]:\n",
    "                        fa[find(x * n + y)] = find(i * n + j)\n",
    "            if find(0) == find(n * n - 1):  # 写这里判断更快些\n",
    "                return d\n",
    "        return 0\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-the-safest-path-in-a-grid/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        ret = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        steal = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                grid[i][j] = inf\n",
    "        for x, y in steal:\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if (i, j) not in steal:\n",
    "                        d = abs(i - x) + abs(j - y)\n",
    "                        grid[i][j] = min(grid[i][j], d)\n",
    "        d = [(1, 0), (0, 1)]\n",
    "        @cache\n",
    "        def dfs(x, y, cnt):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return cnt\n",
    "            ret = 0\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < m and ny < n and grid[nx][ny] < inf:\n",
    "                    ret = max(ret, dfs(nx, ny, min(cnt, grid[nx][ny])))\n",
    "            return ret     \n",
    "        return dfs(0, 0, grid[0][0])             \n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        steal = []\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "        groups = [steal]\n",
    "        while steal:\n",
    "            tmp = steal\n",
    "            steal = []\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                        steal.append((nx, ny))\n",
    "                        distance[nx][ny] = len(groups)\n",
    "            groups.append(steal)\n",
    "        def check(x):\n",
    "            p = list(range(n * n))\n",
    "            def find(x):\n",
    "                if p[x] == x:\n",
    "                    return x\n",
    "                p[x] = find(p[x])\n",
    "                return p[x]\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    k = i * n + j\n",
    "                    if distance[i][j] <= x:\n",
    "                        if i < n - 1 and distance[i+1][j] <= x:\n",
    "                            p[find(k+n)] = find(k)\n",
    "                        if j < n - 1 and distance[i][j+1] <= x:\n",
    "                            p[find(k+1)] = find(k)\n",
    "            return find(0) == find(n * n - 1)\n",
    "        left, right = 0, len(groups)\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        steal = []\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "\n",
    "        groups = [steal]\n",
    "        while steal:\n",
    "            tmp = steal\n",
    "            steal = []\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                        steal.append((nx, ny))\n",
    "                        distance[nx][ny] = len(groups)\n",
    "            groups.append(steal)\n",
    "\n",
    "        p = list(range(n * n))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        for g in range(len(groups)-2, 0, -1):\n",
    "            for x, y in groups[g]:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] >= distance[x][y]:\n",
    "                        p[find(nx * n + ny)] = find(x * n + y)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                return g\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=[]\n",
    "        dis=[[-1 for _ in range(n)]for _ in range(n)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                if x:\n",
    "                    q.append((i,j))\n",
    "                    dis[i][j]=0\n",
    "        groups = [q]\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if 0<=x<n and 0<=y<n and dis[x][y]<0:\n",
    "                        q.append((x, y))\n",
    "                        dis[x][y]=len(groups)\n",
    "            groups.append(q)\n",
    "        grid=dis\n",
    "        #print(grid)\n",
    "        def canget(k):\n",
    "            dp=[[False for _ in range(n)]for _ in range(m)]\n",
    "            q=[(0,0)]\n",
    "            while q:\n",
    "                a,b=q.pop()\n",
    "                #print(a,b,grid[a][b],k)\n",
    "                if grid[a][b]<k:\n",
    "                    continue\n",
    "                if dp[a][b]:\n",
    "                    continue\n",
    "                dp[a][b]=True\n",
    "                if a==m-1 and b==n-1:\n",
    "                    #print(k,True)\n",
    "                    return True\n",
    "                if a<0 or b<0 or a>=m or b>=n:\n",
    "                    continue\n",
    "                if a>0 and not dp[a-1][b]:\n",
    "                    q.append((a-1,b))\n",
    "                if a<m-1 and not dp[a+1][b]:\n",
    "                    q.append((a+1,b))\n",
    "                if b>0 and not dp[a][b-1]:\n",
    "                    q.append((a,b-1))\n",
    "                if b<n-1 and not dp[a][b+1]:\n",
    "                    q.append((a,b+1))\n",
    "           #print(k,False)\n",
    "            return False\n",
    "        l,h=0,min(grid[0][0],grid[-1][-1])\n",
    "        #ans=bisect.bisect_left(range(0,min(grid[0][0],grid[-1][-1])),True,key=canget)\n",
    "        if canget(h):\n",
    "            return h\n",
    "        if not canget(1):\n",
    "            return 0\n",
    "        while l<h-1:\n",
    "            mid=(l+h)//2\n",
    "            if canget(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                h=mid\n",
    "        if canget(h):\n",
    "            return h\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(p, q):\n",
    "            P = find(p)\n",
    "            Q = find(q)\n",
    "            if P == Q:\n",
    "                return\n",
    "            parent[P] = Q\n",
    "        \n",
    "        n = len(grid)\n",
    "        q = []\n",
    "        dis = [[-1]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i, j))\n",
    "                    dis[i][j] = 0\n",
    "        groups = [q]\n",
    "        dirc = [(0,1), (0,-1), (1,0), (-1,0)]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for dic in dirc:\n",
    "                    x = i + dic[0]\n",
    "                    y = j + dic[1]\n",
    "                    if 0<=x<n and 0<=y<n and dis[x][y]<0:\n",
    "                        q.append((x,y))\n",
    "                        dis[x][y] = len(groups)\n",
    "            groups.append(q)\n",
    "        \n",
    "        parent = list(range(n*n))\n",
    "        for ans in range(len(groups)-2, 0, -1):\n",
    "            for i, j in groups[ans]:\n",
    "                for dic in dirc:\n",
    "                    x = i + dic[0]\n",
    "                    y = j + dic[1]\n",
    "                    if 0<=x<n and 0<=y<n and dis[x][y]>=dis[i][j]:\n",
    "                        union(x*n+y, i*n+j)\n",
    "            if find(0) == find(n*n-1):\n",
    "                return ans\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dirs = [[1,0], [0,1], [-1,0], [0,-1]]\n",
    "        q = []\n",
    "        risk = [[1e9]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i,j,0))\n",
    "                    risk[i][j] = 0\n",
    "                    \n",
    "        \n",
    "        for i, j, dis in q:\n",
    "            for di, dj in dirs:\n",
    "                ii, jj = i+di, j+dj\n",
    "                if 0<=ii<n and 0<=jj<n and (dis+1)<risk[ii][jj]:\n",
    "                    q.append((ii, jj, dis+1))\n",
    "                    risk[ii][jj] = dis+1\n",
    "        \n",
    "        def judge(lim):\n",
    "            vis = [[0]*n for _ in range(n)]\n",
    "            vis[0][0] = 1\n",
    "            q = [(0, 0)]\n",
    "            for i, j in q:\n",
    "                for di, dj in dirs:\n",
    "                    ii, jj = i+di, j+dj\n",
    "                    if 0<=ii<n and 0<=jj<n and vis[ii][jj]==0 and risk[ii][jj]>=lim:\n",
    "                        q.append((ii,jj))\n",
    "                        vis[ii][jj] = 1\n",
    "            return vis[n-1][n-1]\n",
    "        \n",
    "        left, right = 0, min(risk[0][0], risk[n-1][n-1])\n",
    "        ans=left\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            print(mid)\n",
    "            if judge(mid):\n",
    "                ans = mid\n",
    "                left = mid+1\n",
    "                \n",
    "            else:\n",
    "                right = mid-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        from math import inf\n",
    "        Bomb = [[inf] * m for _ in range(0,n)]\n",
    "        que = []\n",
    "        directs = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        for i in range(0,n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.append([0,i,j])\n",
    "                    Bomb[i][j] = 0\n",
    "        \n",
    "        import heapq\n",
    "        vst = set()\n",
    "        while que:\n",
    "            weight,x,y = heapq.heappop(que)\n",
    "            if (x,y) in vst:\n",
    "                continue\n",
    "            vst.add((x,y))\n",
    "            Bomb[x][y] = weight\n",
    "            for direct in directs:\n",
    "                nx = x + direct[0]\n",
    "                ny = y + direct[1]\n",
    "                if nx < 0 or ny < 0 or nx >= n or ny >= m or (nx,ny) in vst:\n",
    "                    continue\n",
    "                heapq.heappush(que,[weight+1,nx,ny])\n",
    "\n",
    "        que = []\n",
    "        vst = set()\n",
    "        x1,y1 = 0,0\n",
    "        x2,y2 = n-1,m-1\n",
    "        que.append([-Bomb[x1][y1],x1,y1])\n",
    "        while que:\n",
    "            dis, x, y = heapq.heappop(que)\n",
    "            if x == x2 and y == y2:\n",
    "                return -dis\n",
    "            if (x, y) in vst:\n",
    "                continue\n",
    "            vst.add((x, y))\n",
    "            for direct in directs:\n",
    "                nx = x + direct[0]\n",
    "                ny = y + direct[1]\n",
    "                if nx < 0 or ny < 0 or nx >= n or ny >= m or (nx, ny) in vst:\n",
    "                    continue\n",
    "                heapq.heappush(que, [-min(-dis, Bomb[nx][ny]), nx, ny])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "\n",
    "        def check(high):\n",
    "            if grid[0][0] < high or grid[-1][-1] < high: return 0\n",
    "            q = deque([(0, 0)])\n",
    "            visited = set(q)\n",
    "            while q:\n",
    "                tmp, q = q, []\n",
    "                for i, j in tmp:\n",
    "                    if (i, j) == (n - 1, n - 1): return 1\n",
    "                    for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in visited and grid[ni][nj] >= high:\n",
    "                            visited.add((ni, nj))\n",
    "                            q.append((ni, nj))\n",
    "            return 0\n",
    "        \n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i, j, 0))\n",
    "                    grid[i][j] = 0\n",
    "                else:\n",
    "                    grid[i][j] = inf\n",
    "\n",
    "        visited = set(q)\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for i, j, d in tmp:\n",
    "                d += 1\n",
    "                for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                    ni, nj = i + di, j + dj\n",
    "                    if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in visited and grid[ni][nj] > d:\n",
    "                        grid[ni][nj] = d\n",
    "                        visited.add((ni, nj))\n",
    "                        q.append((ni, nj, d))\n",
    "                        \n",
    "        return 2 * n - bisect_left(range(2 * n, -1, -1), 1, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "move = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        counter = defaultdict(int)\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    counter[i, j] = 0\n",
    "                    queue.append([0, i, j])\n",
    "\n",
    "        def find_neighbor(r, c):\n",
    "            res = []\n",
    "            move = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "            for i1, j1 in move:\n",
    "                if (r + i1, c + j1) not in counter:\n",
    "                    if 0 <= r + i1 < n and 0 <= c + j1 < n:\n",
    "                        res.append((r + i1, c + j1))\n",
    "            return res\n",
    "\n",
    "        while queue:\n",
    "            dis, i, j = queue.popleft()\n",
    "            for i1, j1 in move:\n",
    "                if (i + i1, j + j1) not in counter:\n",
    "                    if 0 <= i + i1 < n and 0 <= j + j1 < n:\n",
    "                        counter[i + i1, j + j1] = dis + 1\n",
    "                        queue.append([dis + 1, i + i1, j + j1])\n",
    "\n",
    "        hq = [[-counter[0, 0], 0, 0]]\n",
    "        counter2 = defaultdict(int)\n",
    "        while hq:\n",
    "            dis, x, y = heapq.heappop(hq)\n",
    "            if (x, y) in counter2:\n",
    "                continue\n",
    "            else:\n",
    "                counter2[x, y] = 1\n",
    "            if x == n - 1 and y == n - 1:\n",
    "                return -dis\n",
    "            for i1, j1 in move:\n",
    "                if (x + i1, y + j1) not in counter2:\n",
    "                    if 0 <= x + i1 < n and 0 <= y + j1 < n:\n",
    "                        heapq.heappush(hq, [-min(-dis, counter[x + i1, y + j1]), x + i1, y + j1])\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        R,C = len(grid), len(grid[0])\n",
    "        # multi-source BFS\n",
    "        Q = []\n",
    "        dis = [[-1] *C for _ in range(R)]\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, v in enumerate(row):\n",
    "                if v :\n",
    "                    dis[r][c] = 0\n",
    "                    Q.append((r,c))\n",
    "        groups = []\n",
    "        groups.append(Q)\n",
    "        while Q:\n",
    "            cur = Q\n",
    "            Q = []\n",
    "            for r,c in cur:\n",
    "                for dr,dc in pairwise([-1,0,1,0,-1]):\n",
    "                    nr,nc = r+dr,c+dc\n",
    "                    if 0<=nr<R and 0<=nc<C and dis[nr][nc] < 0:\n",
    "                        dis[nr][nc] = len(groups)\n",
    "                        Q.append((nr,nc))\n",
    "            groups.append(Q)\n",
    "        fa = {}\n",
    "        def find(x):\n",
    "            if x not in fa:\n",
    "                fa[x] = x\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for d in range(len(groups)-2,-1, -1):    \n",
    "            for r,c in groups[d]:\n",
    "                for dr,dc in pairwise([-1,0,1,0,-1]):\n",
    "                    nr,nc = r+dr,c+dc\n",
    "                    if 0<=nr<R and 0<=nc<C and dis[nr][nc] >= dis[r][c]:\n",
    "                        fa[find((nr,nc))] = find((r,c))\n",
    "            if find((0,0))  == find((R-1,C-1)):            \n",
    "                return d\n",
    "        return 0\n",
    "                \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        # 最大的最小值\n",
    "        n=len(grid)\n",
    "        d={}\n",
    "        grid1=[]\n",
    "        directions=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        maxsafty=0\n",
    "        def calculate():\n",
    "            dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "            q = []\n",
    "            used = set()\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        d[(i,j)]=0\n",
    "                        q.append((i, j))\n",
    "                        used.add((i, j))\n",
    "            dis = 0\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                dis += 1\n",
    "                for x, y in tmp:\n",
    "                    for i, j in dirs:\n",
    "                        r = x + i\n",
    "                        c = y + j\n",
    "                        if 0 <= r < n and 0 <= c < n and (r, c) not in used:\n",
    "                            if grid[r][c] == 0:\n",
    "                                nonlocal maxsafty\n",
    "                                d[(r,c)] = dis\n",
    "                                maxsafty=max(maxsafty,d[(r,c)])\n",
    "                                q.append((r, c))\n",
    "                                used.add((r, c))\n",
    "\n",
    "        def check(minsafty):\n",
    "            q=deque()\n",
    "            used=set()\n",
    "            if d[(0,0)]<minsafty:\n",
    "                return False\n",
    "            q.append((0,0))\n",
    "            used.add((0,0))\n",
    "            if 0 == n - 1 and 0 == n - 1:\n",
    "                return True\n",
    "            while q:\n",
    "                i,j=q.popleft()\n",
    "                for dt in directions:\n",
    "                    x,y=i+dt[0],j+dt[1]\n",
    "                    if 0<=x<n and 0<=y<n and (x,y) not in used and d[(x,y)]>=minsafty:\n",
    "                        if x == n - 1 and y == n - 1:\n",
    "                            return True\n",
    "                        q.append((x,y))\n",
    "                        used.add((x,y))\n",
    "            return False\n",
    "        calculate()\n",
    "        # left,right=0,n+n\n",
    "        left,right=0,maxsafty+1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        distance, queue, towards = {}, [], [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]:\n",
    "                    queue.append((i, j))\n",
    "                    distance[(i, j)] = 0\n",
    "        while queue:\n",
    "            queueNext = []\n",
    "            for x in queue:\n",
    "                for y in towards:\n",
    "                    if 0 <= x[0] + y[0] < len(grid) and 0 <= x[1] + y[1] < len(grid[0]) and (x[0] + y[0], x[1] + y[1]) not in distance:\n",
    "                        queueNext.append((x[0] + y[0], x[1] + y[1]))\n",
    "                        distance[(x[0] + y[0], x[1] + y[1])] = distance[x] + 1\n",
    "            queue = queueNext[:]\n",
    "        heap, res, already = [[-distance[(0, 0)], (0, 0)]], distance[(0, 0)], {(0, 0)}\n",
    "        while 1:\n",
    "            pres = heappop(heap)\n",
    "            res = min(res, -pres[0])\n",
    "            if pres[1] == (len(grid) - 1, len(grid[0]) - 1):\n",
    "                return res\n",
    "            for x in towards:\n",
    "                if 0 <= pres[1][0] + x[0] < len(grid) and 0 <= pres[1][1] + x[1] < len(grid[0]) and (pres[1][0] + x[0], pres[1][1] + x[1]) not in already:\n",
    "                        heappush(heap, [-distance[(pres[1][0] + x[0], pres[1][1] + x[1])], (pres[1][0] + x[0], pres[1][1] + x[1])])\n",
    "                        already.add((pres[1][0] + x[0], pres[1][1] + x[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Run multi-source BFS from the thieves to find the distance between any cell and its cloest monster.\n",
    "    Then, run binary search to find the largest distance k such that S has a path to E where every cell on the path is at least k units from a thief.\n",
    "    Then, write a function that runs DFS to determine whether there exists a path from S to E where every cell on the path is at least k units from a thief.\n",
    "    Time complexity: O(n^2log(n^2)). Space complexity: O(n^2).\n",
    "    '''\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dists = [[-1 for _ in range(n)] for _ in range(n)] \n",
    "    \n",
    "        # Run multi-source BFS from the monsters\n",
    "        q = deque([])\n",
    "        discovered = set()\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] == 1:\n",
    "                    q.append((r, c))\n",
    "                    discovered.add((r, c))\n",
    "    \n",
    "        dist = 0\n",
    "        while q:\n",
    "            # Process every cell at the current level\n",
    "            numCells = len(q)\n",
    "            for _ in range(numCells):\n",
    "                r, c = q.popleft()\n",
    "                dists[r][c] = dist\n",
    "                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    nr, nc = r+dr, c+dc\n",
    "                    if (0 <= nr < n) and (0 <= nc < n) and (nr, nc) not in discovered:\n",
    "                        discovered.add((nr, nc))\n",
    "                        q.append((nr, nc))\n",
    "            dist += 1\n",
    "    \n",
    "        # Run DFS to determine whether there exists a path from S to E where every call on the path is at least k units from a thieve\n",
    "        def existsPathKDistant(k):\n",
    "            if dists[0][0] < k:\n",
    "                return False\n",
    "\n",
    "            s = [(0, 0)]\n",
    "            discovered = set()\n",
    "            while s:\n",
    "                r, c = s.pop()\n",
    "                if (r, c) == (n-1, n-1):\n",
    "                    return True\n",
    "                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    nr, nc = r+dr, c+dc\n",
    "                    if (0 <= nr < n) and (0 <= nc < n) and dists[nr][nc] >= k and (nr, nc) not in discovered:\n",
    "                        discovered.add((nr, nc))\n",
    "                        s.append((nr, nc))\n",
    "            return False\n",
    "        \n",
    "        # Run binary search to find the largest k s.t. existsPathKDistant(k) is true\n",
    "        l, r = 0, min(dists[0][0], dists[n-1][n-1])\n",
    "        while l <= r:\n",
    "            k = (l + r) // 2\n",
    "            if existsPathKDistant(k):\n",
    "                ans = k\n",
    "                l = k + 1\n",
    "            else:\n",
    "                r = k - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid);\n",
    "        dis,fa,stk,vis=[(99999,0)]*(n*n),[i for i in range(0,n*n)],[],[[0]*n for i in range(0,n)]\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,n):\n",
    "                if(grid[i][j]==1):stk.append((i,j,0));vis[i][j]=1;dis[i*n+j]=(0,i*n+j)\n",
    "        fx=[(-1,0),(0,-1),(0,1),(1,0)]\n",
    "        x,y=0,len(stk)\n",
    "        while(len(stk)!=n*n):\n",
    "            for i in range(x,y):\n",
    "                for j in range(0,4):\n",
    "                    if(0<=stk[i][0]+fx[j][0]<n and 0<=stk[i][1]+fx[j][1]<n and (not vis[stk[i][0]+fx[j][0]][stk[i][1]+fx[j][1]])):\n",
    "                        vis[stk[i][0]+fx[j][0]][stk[i][1]+fx[j][1]]=1\n",
    "                        dis[(stk[i][0]+fx[j][0])*n+stk[i][1]+fx[j][1]]=(stk[i][2]+1,(stk[i][0]+fx[j][0])*n+stk[i][1]+fx[j][1])\n",
    "                        stk.append((stk[i][0]+fx[j][0],stk[i][1]+fx[j][1],stk[i][2]+1))\n",
    "            x,y=y,len(stk)\n",
    "        dis.sort(reverse=True)\n",
    "        def getfa(u):\n",
    "            nonlocal fa\n",
    "            if(fa[u]==u):return u\n",
    "            else:\n",
    "                fa[u]=getfa(fa[u])\n",
    "                return fa[u]\n",
    "        for i in dis:\n",
    "            p,q=i[1]//n,i[1]%n\n",
    "            vis[p][q]=0\n",
    "            for j in range(0,4):\n",
    "                if(0<=p+fx[j][0]<n and 0<=q+fx[j][1]<n and (not vis[p+fx[j][0]][q+fx[j][1]])):\n",
    "                    t=(p+fx[j][0])*n+q+fx[j][1]\n",
    "                    fa[i[1]],fa[t]=getfa(i[1]),getfa(t)\n",
    "                    if(fa[i[1]]!=fa[t]):fa[fa[t]]=fa[i[1]]\n",
    "            fa[0],fa[n*n-1]=getfa(0),getfa(n*n-1)\n",
    "            if(fa[0]==fa[n*n-1]):return i[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "   如何处理某个多个小偷到达每个格子的最小距离\n",
    "   多源bfs  可将O(n**4)  --> O(n ** 2)\n",
    "   之后利用二分法进行搜索答案即可\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        # 预处理每个格子到达小偷的最短距离\n",
    "        n = len(grid)\n",
    "        if n==1: return 0\n",
    "        dist = [[inf]*n for _ in range(n)]\n",
    "        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        q = deque()\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dist[i][j] = 0\n",
    "                    q.append([i, j])\n",
    "                    vis.add((i, j))\n",
    "\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx< n and 0<=ny<n and (nx, ny) not in vis:\n",
    "                    dist[nx][ny] = dist[x][y] + 1\n",
    "                    vis.add((nx, ny))\n",
    "                    q.append([nx, ny])\n",
    "        \n",
    "        # 二分答案进行验证\n",
    "        \n",
    "        def check(mid):\n",
    "            # 单源bfs\n",
    "            if dist[0][0] < mid: return False\n",
    "            q = [(0, 0)]\n",
    "            vis = set([(0, 0)])\n",
    "            while q:\n",
    "                x, y = q.pop()\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = x+dx, y+dy\n",
    "                    if 0<=nx<n and 0<=ny<n and dist[nx][ny] >= mid and (nx, ny) not in vis:\n",
    "                        if nx == n-1 and ny == n-1:\n",
    "                            return True\n",
    "                        q.append((nx, ny))\n",
    "                        vis.add((nx, ny))\n",
    "            return False\n",
    "\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else: r = mid\n",
    "        return l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        asked = set()\n",
    "        d = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    asked.add((i, j))\n",
    "                    d.append((i, j, 0))\n",
    "        \n",
    "        distance = defaultdict(int)\n",
    "\n",
    "        while d:\n",
    "            x, y, h = d.popleft()\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                x_, y_ = x + dx, y + dy\n",
    "                if 0 <= x_ < n and 0 <= y_ < n and (x_, y_) not in asked:\n",
    "                    asked.add((x_, y_))\n",
    "                    distance[(x_, y_)] = h + 1\n",
    "                    d.append((x_, y_, h + 1))\n",
    "        \n",
    "        @cache\n",
    "        def judge(k):\n",
    "            nonlocal n\n",
    "            if distance[(0, 0)] < k or distance[(n - 1, n - 1)] < k:\n",
    "                return False\n",
    "            \n",
    "            d = deque([(0, 0)])\n",
    "            asked = set([(0, 0)])\n",
    "            while d:\n",
    "                x, y = d.popleft()\n",
    "                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                    x_, y_ = x + dx, y + dy\n",
    "                    if x_ == y_ == n - 1:\n",
    "                        return True\n",
    "\n",
    "                    if 0 <= x_ < n and 0 <= y_ < n and (x_, y_) not in asked:\n",
    "                        asked.add((x_, y_))\n",
    "                        if distance[(x_, y_)] >= k:\n",
    "                            d.append((x_, y_))\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        left, right = 0, n\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "            if judge(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        if judge(right):\n",
    "            return right\n",
    "        else:\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        visited = set()\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        queue = []\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, num in enumerate(line):\n",
    "                if num == 1:\n",
    "                    queue.append((0, i, j))\n",
    "        idx = 0\n",
    "        while idx < len(queue):\n",
    "            depth, x, y = queue[idx]\n",
    "            idx += 1\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            ans[x][y] = depth\n",
    "            visited.add((x, y))\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:\n",
    "                    queue.append((depth + 1, nx, ny))\n",
    "        visited = set()\n",
    "        heap = [(-ans[0][0], 0, 0)]\n",
    "        while heap:\n",
    "            depth, x, y = heapq.heappop(heap)\n",
    "            depth = -depth\n",
    "            if x == y == n - 1:\n",
    "                return depth\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            visited.add((x, y))\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:\n",
    "                    heapq.heappush(heap, (-min(depth, ans[nx][ny]), nx, ny))\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1:  # 特判\n",
    "            return 0\n",
    "\n",
    "        dis = defaultdict(lambda: -1)\n",
    "        # 找到所有小偷\n",
    "        dq = deque()\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dq.append((i, j, 0))\n",
    "                    dis[(i, j)] = 0\n",
    "\n",
    "        # 多源bfs, 同时记录(i, j, d)三元组\n",
    "        rec = []\n",
    "        while dq:\n",
    "            i, j, d = dq.popleft()\n",
    "            rec.append((i, j, d))\n",
    "            for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if 0 <= ni < n and 0 <= nj < n and dis[(ni, nj)] == -1:\n",
    "                    dis[(ni, nj)] = d + 1\n",
    "                    dq.append((ni, nj, d + 1))\n",
    "\n",
    "        # 并查集\n",
    "        fa = list(range(n * n))\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        rec.sort(key=lambda x: -x[2])  # sort by distance\n",
    "        # 取出最长的,并把周边>=d的格子用并查集连起来,检查(0,0)和(n-1, n-1)之间的连通性\n",
    "        for x, y, d in rec:\n",
    "            for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "                if 0 <= nx < n and 0 <= ny < n and dis[(nx, ny)] >= d:\n",
    "                    fa[find(nx * n + ny)] = find(x * n + y)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                return d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        n = len(grid)\n",
    "        \n",
    "        dis = [[-1 for _ in range(n)] for _ in range(n)]\n",
    "        thiefs = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] == 1:\n",
    "                    thiefs.append((i, j))\n",
    "                    dis[i][j] = 0\n",
    "        q = thiefs\n",
    "        i = 1\n",
    "        while len(q) > 0:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for v in tmp:\n",
    "                for d in dirs:\n",
    "                    ni, nj = v[0] + d[0], v[1] + d[1]\n",
    "                    if 0 <= ni < n and 0 <= nj < n and dis[ni][nj] < 0:\n",
    "                        dis[ni][nj] = i\n",
    "                        q.append((ni, nj))\n",
    "            i += 1\n",
    "        vis = [-1] * (n * n)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(i, j, mi):\n",
    "            nonlocal ans\n",
    "            if i == n - 1 and j == n - 1:\n",
    "                ans = max(ans, mi)\n",
    "                return\n",
    "            \n",
    "            ha = i * n + j\n",
    "            if mi <= ans or mi <= vis[ha]:\n",
    "                return\n",
    "            \n",
    "            vis[ha] = max(vis[ha], mi)\n",
    "            \n",
    "            for d in dirs:\n",
    "                ni, nj = i + d[0], j + d[1]\n",
    "                if 0 <= ni < n and 0 <= nj < n:\n",
    "                    dfs(ni, nj, min(mi, dis[ni][nj]))\n",
    "        dfs(0, 0, min(dis[0][0], dis[n - 1][n - 1]))\n",
    "        return ans \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dir_x, dir_y = (-1, 1, 0, 0), (0, 0, -1, 1)\n",
    "        secure = defaultdict(lambda: inf)\n",
    "        fa = list(range(n * n))\n",
    "        q = deque()\n",
    "        \n",
    "        for i, line in enumerate(grid):\n",
    "            for j, v in enumerate(line):\n",
    "                if not v: continue\n",
    "                q.append((i, j))\n",
    "                secure[i, j] = 0\n",
    "\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in zip(dir_x, dir_y):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in secure:\n",
    "                    secure[nx, ny] = secure[x, y] + 1\n",
    "                    q.append((nx, ny))\n",
    "\n",
    "        def find_root(x):\n",
    "            if fa[x] != x: fa[x] = find_root(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            rx = find_root(x)\n",
    "            ry = find_root(y)\n",
    "            if rx != ry: fa[ry] = rx\n",
    "        \n",
    "        seen = set()\n",
    "        for (x, y), w in sorted(secure.items(), key=lambda x: -x[1]):\n",
    "            seen.add((x, y))\n",
    "            for dx, dy in zip(dir_x, dir_y):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in seen: merge(x * n + y, nx * n + ny)\n",
    "            if find_root(0) == find_root(n * n - 1): return w\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        from collections import deque\n",
    "        # bfs to find minimum distance from any monster\n",
    "        n = len(grid)\n",
    "        neighbors = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        dist = [[1000]*n for i in range(n)]\n",
    "        tovisit = deque([])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    tovisit.append((i,j))\n",
    "                    dist[i][j] = 0\n",
    "        print(tovisit)\n",
    "        while tovisit:\n",
    "            x,y = tovisit.popleft()\n",
    "            for dx,dy in neighbors:\n",
    "                new_x,new_y = x+dx, y+dy\n",
    "                if 0<=new_x<n and 0<=new_y<n and dist[new_x][new_y] > dist[x][y] + 1:\n",
    "                    dist[new_x][new_y] = dist[x][y] + 1\n",
    "                    tovisit.append((new_x,new_y))\n",
    "        # binary search for answer\n",
    "        def check_ans(max_safeness):\n",
    "            visited = [[False]*n for i in range(n)]\n",
    "            results = [[True]*n for i in range(n)]\n",
    "            def dfs(x,y):\n",
    "                # print(x,y)\n",
    "                if dist[x][y] < max_safeness:\n",
    "                    results[x][y] = False\n",
    "                    return False\n",
    "                if x == n-1 and y == n-1:\n",
    "                    return True\n",
    "                visited[x][y] = True\n",
    "                for dx,dy in neighbors:\n",
    "                    new_x,new_y = x+dx, y+dy\n",
    "                    if 0<=new_x<n and 0<=new_y<n and not visited[new_x][new_y] and results[new_x][new_y] and dfs(new_x,new_y):\n",
    "                        return True\n",
    "                visited[x][y] = False\n",
    "                results[x][y] = False\n",
    "                return False\n",
    "            return dfs(0,0)\n",
    "        left,right = 0,min(dist[0][0],dist[-1][-1])+1\n",
    "        while left+1<right:\n",
    "            mid = (left+right)//2\n",
    "            if check_ans(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        # use dijkstra for answer\n",
    "        # for i in dist:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # from heapq import heapify, heappop, heappush\n",
    "        # mind = [[0]*n for i in range(n)]\n",
    "        # pq = [(-dist[0][0],0,0)]\n",
    "        # heapify(pq)\n",
    "        # while pq:\n",
    "        #     d,x,y = heappop(pq)\n",
    "        #     if x == n-1 and y == n-1:\n",
    "        #         break\n",
    "        #     for dx,dy in neighbors:\n",
    "        #         new_x,new_y = x+dx, y+dy\n",
    "        #         if 0<=new_x<n and 0<=new_y<n:\n",
    "        #             cur = max(-dist[new_x][new_y],d)\n",
    "        #             # print(new_x,new_y,cur)\n",
    "        #             if mind[new_x][new_y] > cur:\n",
    "        #                 mind[new_x][new_y] = cur\n",
    "        #                 heappush(pq, ((mind[new_x][new_y],new_x,new_y)))\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         possibilities = []\n",
    "        #         if i > 0:\n",
    "        #             possibilities.append(dist[i-1][j])\n",
    "        #         if j>0:\n",
    "        #             possibilities.append(dist[i][j-1])\n",
    "        #         dist[i][j] = min(dist[i][j],max(possibilities) if possibilities else dist[i][j])\n",
    "        # for i in mind:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # return -mind[-1][-1]\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def is_feasible(grid, threshold):\n",
    "    m, n = len(grid), len(grid[0])\n",
    "    visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "    def dfs(i, j):\n",
    "        if i == m - 1 and j == n - 1:\n",
    "            return True\n",
    "        visited[i][j] = True\n",
    "        for dx, dy in [(0, 1), (1, 0),(-1,0),(0,-1)]:\n",
    "            x, y = i + dx, j + dy\n",
    "            if 0 <= x < m and 0 <= y < n and not visited[x][y] and grid[x][y] >= threshold:\n",
    "                if dfs(x, y):\n",
    "                    return True\n",
    "        return False\n",
    "    return dfs(0, 0) if grid[0][0] >= threshold else False\n",
    "\n",
    "def maximum_minimum_path(grid):\n",
    "    left, right = 0,800\n",
    "    #print(left,right)\n",
    "    while left < right:\n",
    "        mid = (left+right+1) //2\n",
    "        if is_feasible(grid, mid):\n",
    "            left = mid \n",
    "        else:\n",
    "            right = mid -1\n",
    "    return right\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        dist = [[-1] * C for _ in range(R)]\n",
    "        from collections import deque\n",
    "        Q = deque()\n",
    "        # print(grid)\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                if grid[r][c] == 1:\n",
    "                    Q.append((r, c))\n",
    "                    dist[r][c] = 0\n",
    "        aux = set(Q)\n",
    "        if (R-1, C-1)  in aux or (0,0) in aux:\n",
    "            return 0\n",
    "        # print(Q)\n",
    "        while Q:\n",
    "            r, c = Q.popleft()\n",
    "            for dr, dc in [[-1, 0], [0, 1], [1, 0], [0, -1]]:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1:\n",
    "                    dist[nr][nc] = dist[r][c] + 1\n",
    "                    Q.append((nr, nc))\n",
    "\n",
    "        return maximum_minimum_path(dist)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        ret = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        steal = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                grid[i][j] = inf\n",
    "        for x, y in steal:\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if (i, j) not in steal:\n",
    "                        d = abs(i - x) + abs(j - y)\n",
    "                        grid[i][j] = min(grid[i][j], d)\n",
    "        d = [(1, 0), (0, 1)]\n",
    "        @cache\n",
    "        def dfs(x, y, cnt):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return cnt\n",
    "            ret = 0\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < m and ny < n and grid[nx][ny] < inf:\n",
    "                    ret = max(ret, dfs(nx, ny, min(cnt, grid[nx][ny])))\n",
    "            return ret     \n",
    "        return dfs(0, 0, grid[0][0])             \n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        steal = []\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "\n",
    "        groups = [steal]\n",
    "        while steal:\n",
    "            tmp = steal\n",
    "            steal = []\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                        steal.append((nx, ny))\n",
    "                        distance[nx][ny] = len(groups)\n",
    "            groups.append(steal)\n",
    "\n",
    "        p = list(range(n * n))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        for g in range(len(groups)-2, 0, -1):\n",
    "            for x, y in groups[g]:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] >= distance[x][y]:\n",
    "                        p[find(nx * n + ny)] = find(x * n + y)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                return g\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                    q.append((nx, ny))\n",
    "                    distance[nx][ny] = distance[x][y] + 1\n",
    "        def check(k):\n",
    "            p = list(range(n * n))\n",
    "            def find(x):\n",
    "                if p[x] == x:\n",
    "                    return x\n",
    "                p[x] = find(p[x])\n",
    "                return p[x]\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if distance[x][y] >= k:\n",
    "                        for dx, dy in d[:2]:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < n > ny >= 0 and distance[nx][ny] >= k:\n",
    "                                # union(nx * n + ny, x * n + y)\n",
    "                                p[find(nx * n + ny)] = find(x * n + y)\n",
    "            return find(0) == find(n * n - 1)\n",
    "        left, right = 0, n << 1\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        \n",
    "        uf = dict()\n",
    "        q = []\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, d in enumerate(row):\n",
    "                uf[(i, j)] = (i, j)\n",
    "                if d == 1: \n",
    "                    q.append((i, j))\n",
    "                    dist[i][j] = 0\n",
    "        dist_list = []            \n",
    "        dist_list.append(q.copy())\n",
    "        while q:            \n",
    "            tmp = q\n",
    "            q = []\n",
    "            while tmp:\n",
    "                i, j = tmp.pop()\n",
    "                for dx, dy in ((-1, 0), (1,0), (0, 1), (0, -1)):\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n: continue\n",
    "                    if grid[x][y] == 1: continue    \n",
    "                    if dist[i][j] + 1 >= dist[x][y]: continue\n",
    "                    dist[x][y] = dist[i][j] + 1    \n",
    "                    q.append((x, y))\n",
    "            if q:        \n",
    "                dist_list.append(q.copy())        \n",
    "        # print(dist_list)\n",
    "        def find(a):\n",
    "            if uf[a] != a:\n",
    "                \n",
    "                pa = find(uf[a])\n",
    "                uf[a] = pa\n",
    "                return pa\n",
    "            return a\n",
    "        def union(a, b):\n",
    "            pa = find(a)\n",
    "            pb = find(b)\n",
    "            uf[pa] = pb\n",
    "        for d in range(len(dist_list) - 1, 0, -1):    \n",
    "            for i, j in dist_list[d]:\n",
    "                for (x, y) in ((i - 1, j), (i+1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if x < 0 or y < 0 or x >= n or y >= n: continue\n",
    "                    if dist[i][j] <= dist[x][y]:\n",
    "                        union((x, y), (i, j))\n",
    "            # print(d, uf)            \n",
    "            if find((0, 0)) == find((n-1, n - 1)): return d\n",
    "        return 0    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(grid)\n",
    "        \n",
    "        def check():\n",
    "            if grid[0][0] or grid[n - 1][n - 1]:\n",
    "                return False\n",
    "            vis = [[False] * n for _ in range(n)]\n",
    "            def dfs(i, j):\n",
    "                vis[i][j] = True\n",
    "                if i == n - 1 and j == n - 1:\n",
    "                    return True\n",
    "                for ni, nj in [(i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)]:\n",
    "                    if 0 <= ni < n and 0 <= nj < n and not vis[ni][nj] and grid[i][j] == 0:\n",
    "                        res = dfs(ni, nj)\n",
    "                        if res:\n",
    "                            return True\n",
    "                return False\n",
    "            return dfs(0, 0)\n",
    "        \n",
    "        if not check():\n",
    "            return 0\n",
    "        \n",
    "        propagate = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    propagate.append((i, j))\n",
    "\n",
    "        for distance in range(1, n):\n",
    "            nxt = []\n",
    "            for i, j in propagate:\n",
    "                for ni, nj in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:\n",
    "                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 0:\n",
    "                        nxt.append((ni, nj))\n",
    "                        grid[ni][nj] = 1\n",
    "            if not check():\n",
    "                return distance\n",
    "            propagate = nxt\n",
    "        \n",
    "        return n - 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append([i, j])\n",
    "                    dis[i][j] = 0\n",
    "        g = [q] # 分组\n",
    "        while q:\n",
    "            tq = q\n",
    "            q = []\n",
    "            for x, y in tq:\n",
    "                for X, Y in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= X < n and 0 <= Y < n and dis[X][Y] == -1:\n",
    "                        dis[X][Y] = len(g)\n",
    "                        q.append([X, Y])\n",
    "            g.append(q)\n",
    "        \n",
    "        fa = list(range(n * n))\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                return find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "            # fx = find(fa[x])\n",
    "            # fy = find(fa[y])\n",
    "            # fa[fx] = fy\n",
    "\n",
    "        for d in range(len(g) - 2, 0, -1):\n",
    "            for x, y in g[d]:\n",
    "                for X, Y in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= X < n and 0 <= Y < n and dis[X][Y] >= dis[x][y]:\n",
    "                        merge(x * n + y, X * n + Y)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                return d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1: return 0\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    q.append((i, j, 0))\n",
    "                    dis[i][j] = 0\n",
    "\n",
    "        mx_d = 0\n",
    "        while q:\n",
    "            i, j, d = q.popleft()\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = dx + i, dy + j\n",
    "                if 0 <= _x < n and 0 <= _y < n and dis[_x][_y] == -1:\n",
    "                    dis[_x][_y] = d + 1\n",
    "                    mx_d = max(mx_d, d + 1)\n",
    "                    q.append((_x, _y, d + 1))\n",
    "\n",
    "        def check(i: int, j: int, v: int) -> bool:\n",
    "            return 0 <= i < n and 0 <= j < n and vis[i][j] != v and dis[i][j] >= v\n",
    "\n",
    "        def dfs(i: int, j:int, v: int) -> bool:\n",
    "            if i == n - 1 and j == n - 1: return True\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = i + dx, j + dy\n",
    "                if check(_x, _y, v):\n",
    "                    vis[_x][_y] = v # 置为 True\n",
    "                    if dfs(_x, _y, v): return True\n",
    "                    # 如果 dfs 是 False，表示不存在这个点通往终点的满足约束的路径，自然也就不用置 False\n",
    "            return False\n",
    "\n",
    "        vis = [[-1] * n for _ in range(n)] \n",
    "\n",
    "        l, r = 0, mx_d\n",
    "        while d:\n",
    "            # m = (l + r) >> 1\n",
    "            if dis[0][0] >= d and dfs(0, 0, d): \n",
    "                return d\n",
    "            d -= 1\n",
    "        return 0\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0]==1 or grid[n-1][n-1]==1:\n",
    "            return 0\n",
    "        e = [[-1 for i in range(n)] for j in range(n)]\n",
    "        ls = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    e[i][j]=0\n",
    "                    ls.append((i,j))\n",
    "        q = deque([ls])\n",
    "        # print(e,q)\n",
    "        mhd = 1\n",
    "        while q:\n",
    "            ls = []\n",
    "            tmp = q.popleft()\n",
    "            # print(tmp)\n",
    "            for x,y in tmp:\n",
    "                for a,b in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0<=a<n and 0<=b<n and e[a][b]==-1:\n",
    "                        e[a][b]=mhd\n",
    "                        ls.append((a,b))\n",
    "            if len(ls)>0:\n",
    "                q.append(ls)\n",
    "                mhd += 1\n",
    "        if mhd == 1:\n",
    "            return 0\n",
    "        # print(e)\n",
    "        ls = []\n",
    "        def bfs(x,y,k):\n",
    "            if x==n-1 and y == n-1:\n",
    "                ls.append((x,y))\n",
    "                return\n",
    "            for a,b in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                if 0<=a<n and 0<=b<n and tmp[a][b]>=k:\n",
    "                    tmp[a][b] = -1\n",
    "                    bfs(a,b,k)\n",
    "\n",
    "        for i in range(mhd,-1,-1):\n",
    "            if i>e[0][0]:\n",
    "                continue\n",
    "            tmp = [[] for j in range(n)]\n",
    "            for j in range(n):\n",
    "                tmp[j] = e[j].copy()\n",
    "            bfs(0,0,i)\n",
    "            if len(ls)>0:\n",
    "                # print(tmp)\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXINT = 10**18\n",
    "\n",
    "def dijkstra(list_of_indexes_and_costs, start):\n",
    "    # shortest path with nonnegative edge costs\n",
    "    # leetcode.com/problems/path-with-maximum-probability/\n",
    "    # leetcode.com/problems/network-delay-time/\n",
    "    length = len(list_of_indexes_and_costs)\n",
    "    visited = [False]*length\n",
    "    weights = [MAXINT]*length\n",
    "    path = [None]*length\n",
    "    queue = []\n",
    "    weights[start] = 0\n",
    "    heapq.heappush(queue, (0, start))\n",
    "    while queue:\n",
    "        g, u = heapq.heappop(queue)\n",
    "        if visited[u]:\n",
    "            continue\n",
    "        visited[u] = True\n",
    "        for v, w in list_of_indexes_and_costs[u]:\n",
    "            if not visited[v]:\n",
    "                f = max(g, w)\n",
    "                if f < weights[v]:\n",
    "                    weights[v] = f\n",
    "                    path[v] = u\n",
    "                    heapq.heappush(queue, (f, v))\n",
    "    return path, weights\n",
    "\n",
    "\n",
    "def dijkstra_with_preprocessing(map_from_node_to_nodes_and_costs, source, target, idxs=set()):\n",
    "    # this operation is costly, recommend to parse to list_of_indexes_and_costs directly\n",
    "    # leetcode.com/problems/path-with-maximum-probability/\n",
    "    # leetcode.com/problems/network-delay-time/\n",
    "    d = map_from_node_to_nodes_and_costs\n",
    "\n",
    "    if target not in d:  # destination may not have outgoing paths\n",
    "        d[target] = []\n",
    "    if source not in d:\n",
    "        return MAXINT\n",
    "\n",
    "    # assign indexes\n",
    "    if idxs:\n",
    "        idxs = {k:i for i,k in enumerate(idxs)}\n",
    "    else:\n",
    "        idxs = {k:i for i,k in enumerate(d.keys())}\n",
    "\n",
    "    # populate list of indexes and costs\n",
    "    list_of_indexes_and_costs = [[] for _ in range(len(idxs))]\n",
    "    for e,vrr in d.items():\n",
    "        for v,cost in vrr:\n",
    "            list_of_indexes_and_costs[idxs[e]].append((idxs[v],cost))\n",
    "\n",
    "    _, costs = dijkstra(list_of_indexes_and_costs, idxs[source])\n",
    "    return costs[idxs[target]]\n",
    "\n",
    "\n",
    "d4 = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        \n",
    "        if n == 1 and m == 1:\n",
    "            return 0\n",
    "        \n",
    "        if grid[0][0] == 1:\n",
    "            return 0\n",
    "        if grid[-1][-1] == 1:\n",
    "            return 0\n",
    "\n",
    "        thieves = set()\n",
    "        \n",
    "        dist = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        \n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid[x][y] == 1:\n",
    "                    thieves.add((x,y))\n",
    "                    dist[x][y] = 0\n",
    "        \n",
    "        queue = deque(thieves)\n",
    "        visited = set(list(thieves))\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            for dx,dy in d4:\n",
    "                xx = x+dx\n",
    "                yy = y+dy\n",
    "                if (xx,yy) in visited:\n",
    "                    continue\n",
    "                if 0 <= xx < n and 0 <= yy < m:\n",
    "                    visited.add((xx,yy))\n",
    "                    queue.append((xx,yy))\n",
    "                    dist[xx][yy] = dist[x][y] + 1\n",
    "        \n",
    "        # for row in dist:\n",
    "        #     print(row)\n",
    "        # print()\n",
    "        \n",
    "        def encode(x,y):\n",
    "            return n*x + y\n",
    "        \n",
    "        g = [[] for _ in range(n*m)]\n",
    "        \n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                for dx,dy in d4:\n",
    "                    xx = x+dx\n",
    "                    yy = y+dy\n",
    "                    if 0 <= xx < n and 0 <= yy < m:\n",
    "                        mindist = min(dist[x][y], dist[xx][yy])\n",
    "                        cost = 1_000_000_000 - mindist\n",
    "                        g[encode(x,y)].append((encode(xx,yy), cost))\n",
    "\n",
    "        # print(g)\n",
    "                    \n",
    "        res = dijkstra(g, 0)[-1][-1]\n",
    "        \n",
    "        # print(res)\n",
    "        \n",
    "        return 1_000_000_000 - res\n",
    "        \n",
    "                \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1:\n",
    "            return 0\n",
    "        queue = Deque([])\n",
    "        v2 = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j, 0))\n",
    "                    v2[(i,j)] = True\n",
    "        while queue:\n",
    "            i, j, step = queue.popleft()\n",
    "            if grid[i][j] == 0:\n",
    "                grid[i][j] = step + 1\n",
    "            neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "            for dx, dy in neighbors:\n",
    "                nx = i + dx\n",
    "                ny = j + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n:\n",
    "                    if (nx, ny) in v2:\n",
    "                        continue\n",
    "                    if grid[nx][ny] == 0:\n",
    "                        queue.append((nx, ny, step+1))\n",
    "                        v2[(nx, ny)] = True\n",
    "        # print(grid)\n",
    "        # return 0\n",
    "        \n",
    "        \n",
    "        def dfs(i, j, threshold):\n",
    "            # print(i, j)\n",
    "            if self.reach_flag:\n",
    "                return\n",
    "            if (i, j) == (n-1, n-1):\n",
    "                self.reach_flag = True\n",
    "                return True\n",
    "            neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "            for dx, dy in neighbors:\n",
    "                nx = i + dx\n",
    "                ny = j + dy\n",
    "                if 0 <= nx < n and 0 <= ny < n:\n",
    "                    if (nx, ny) in self.visited:\n",
    "                        continue\n",
    "                    if grid[nx][ny] > threshold:\n",
    "                        # print(\"****\", nx, ny, grid[nx][ny], threshold)\n",
    "                        self.visited[(nx, ny)] = True\n",
    "                        dfs(nx, ny, threshold)\n",
    "                        \n",
    "                        \n",
    "        \n",
    "        # self.reach_flag = False\n",
    "        max_thres = min(grid[0][0], grid[-1][-1]) - 1\n",
    "        \n",
    "        self.visited = {}\n",
    "        self.visited[(0,0)] = True\n",
    "        for t in range(max_thres, -1, -1):\n",
    "            # print(t)\n",
    "            self.reach_flag = False\n",
    "            v3 = list(self.visited.keys())\n",
    "            for g in v3:\n",
    "                dfs(g[0], g[1], t)\n",
    "            if self.reach_flag:\n",
    "                return t\n",
    "        \n",
    "        \n",
    "                        \n",
    "            \n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1: return 0\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    q.append((i, j, 0))\n",
    "                    dis[i][j] = 0\n",
    "\n",
    "        mx_d = 0\n",
    "        while q:\n",
    "            i, j, d = q.popleft()\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = dx + i, dy + j\n",
    "                if 0 <= _x < n and 0 <= _y < n and dis[_x][_y] == -1:\n",
    "                    dis[_x][_y] = d + 1\n",
    "                    mx_d = max(mx_d, d + 1)\n",
    "                    q.append((_x, _y, d + 1))\n",
    "\n",
    "        def check(i: int, j: int, v: int) -> bool:\n",
    "            return 0 <= i < n and 0 <= j < n and vis[i][j] != v and dis[i][j] >= v\n",
    "\n",
    "        # @cache\n",
    "        def dfs(i: int, j:int, v: int) -> bool:\n",
    "            if i == n - 1 and j == n - 1: return True\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = i + dx, j + dy\n",
    "                if check(_x, _y, v):\n",
    "                    vis[_x][_y] = v\n",
    "                    if dfs(_x, _y, v): return True\n",
    "            return False\n",
    "\n",
    "        vis = [[-1] * n for _ in range(n)]\n",
    "\n",
    "        l, r = 0, mx_d\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            if dis[0][0] >= m and dfs(0, 0, m): \n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1: return 0\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        dis = [[-1] * n for _ in range(n)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    q.append((i, j, 0))\n",
    "                    dis[i][j] = 0\n",
    "\n",
    "        mx_d = 0\n",
    "        while q:\n",
    "            i, j, d = q.popleft()\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = dx + i, dy + j\n",
    "                if 0 <= _x < n and 0 <= _y < n and dis[_x][_y] == -1:\n",
    "                    dis[_x][_y] = d + 1\n",
    "                    mx_d = max(mx_d, d + 1)\n",
    "                    q.append((_x, _y, d + 1))\n",
    "\n",
    "        def check(i: int, j: int, v: int) -> bool:\n",
    "            return 0 <= i < n and 0 <= j < n and vis[i][j] != v and dis[i][j] >= v\n",
    "\n",
    "\n",
    "        def dfs(i: int, j:int, v: int) -> bool:\n",
    "            if i == n - 1 and j == n - 1: return True\n",
    "            for dx, dy in pairwise([1, 0, -1, 0, 1]):\n",
    "                _x, _y = i + dx, j + dy\n",
    "                if check(_x, _y, v):\n",
    "                    vis[_x][_y] = v\n",
    "                    if dfs(_x, _y, v): return True\n",
    "            return False\n",
    "\n",
    "        vis = [[-1] * n for _ in range(n)]\n",
    "\n",
    "        l, r = 0, mx_d\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            if dis[0][0] >= m and dfs(0, 0, m): \n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return r\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, g: List[List[int]]) -> int:\n",
    "        n = len(g)\n",
    "        if g[0][0] == 1 or g[-1][-1] == 1:\n",
    "            return 0\n",
    "        # 能否求出每一个点对小偷的最小距离？\n",
    "        dis = [[inf] * n for _ in range(n)]\n",
    "        q = deque()\n",
    "        vis = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if g[i][j] == 0:\n",
    "                    continue\n",
    "                q.append((i, j, 0))\n",
    "                vis[i][j] = True\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        \n",
    "        while q:\n",
    "            x, y, st = q.popleft()\n",
    "            dis[x][y] = min(st, dis[x][y])\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= n:\n",
    "                    continue\n",
    "                if vis[nx][ny]:\n",
    "                    continue\n",
    "                q.append((nx, ny, st + 1))\n",
    "                vis[nx][ny] = True\n",
    "        \n",
    "        l, r = 0, 1000\n",
    "\n",
    "        # 检查m是否可以，要求路径上所有dis >= m\n",
    "        def check(m):\n",
    "            if dis[-1][-1] < m:\n",
    "                return False\n",
    "\n",
    "            vis = [[False] * n for _ in range(n)]\n",
    "            vis[0][0] = True\n",
    "\n",
    "            def f(x, y):\n",
    "                if dis[x][y] < m:\n",
    "                    return False\n",
    "                if x == n - 1 and y == n - 1:\n",
    "                    return True\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if nx < 0 or nx >= n or ny < 0 or ny >= n:\n",
    "                        continue\n",
    "                    if dis[nx][ny] < m or vis[nx][ny]:\n",
    "                      continue\n",
    "                    vis[nx][ny] = True\n",
    "                    if f(nx, ny):\n",
    "                        return True\n",
    "\n",
    "                return False\n",
    "            \n",
    "            return f(0, 0)\n",
    "        \n",
    "        while l < r:\n",
    "            mid = (r - l + 1) // 2 + l\n",
    "            if not check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        ret = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        steal = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                grid[i][j] = inf\n",
    "        for x, y in steal:\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if (i, j) not in steal:\n",
    "                        d = abs(i - x) + abs(j - y)\n",
    "                        grid[i][j] = min(grid[i][j], d)\n",
    "        d = [(1, 0), (0, 1)]\n",
    "        @cache\n",
    "        def dfs(x, y, cnt):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return cnt\n",
    "            ret = 0\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < m and ny < n and grid[nx][ny] < inf:\n",
    "                    ret = max(ret, dfs(nx, ny, min(cnt, grid[nx][ny])))\n",
    "            return ret     \n",
    "        return dfs(0, 0, grid[0][0])             \n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        steal = []\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    steal.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "\n",
    "        groups = [steal]\n",
    "        while steal:\n",
    "            tmp = steal\n",
    "            steal = []\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                        steal.append((nx, ny))\n",
    "                        distance[nx][ny] = len(groups)\n",
    "            groups.append(steal)\n",
    "\n",
    "        p = list(range(n * n))\n",
    "        def find(x):\n",
    "            if p[x] == x:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        for g in range(len(groups)-2, 0, -1):\n",
    "            for x, y in groups[g]:\n",
    "                for dx, dy in d:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n > ny >= 0 and distance[nx][ny] >= distance[x][y]:\n",
    "                        p[find(nx * n + ny)] = find(x * n + y)\n",
    "            if find(0) == find(n * n - 1):\n",
    "                return g\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]: return 0\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        d = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        distance = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i, j))\n",
    "                    distance[i][j] = 0\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n > ny >= 0 and distance[nx][ny] < 0:\n",
    "                    q.append((nx, ny))\n",
    "                    distance[nx][ny] = distance[x][y] + 1\n",
    "        def check(k):\n",
    "            p = list(range(n * n))\n",
    "            s = [1] * n * n\n",
    "            def find(x):\n",
    "                if p[x] == x:\n",
    "                    return x\n",
    "                p[x] = find(p[x])\n",
    "                return p[x]\n",
    "            def union(x, y):\n",
    "                x_root, y_root = find(x), find(y)\n",
    "                if x_root != y_root:\n",
    "                    if s[y_root] <= s[x_root]:\n",
    "                        p[y_root] = x_root\n",
    "                        s[x_root] += y_root\n",
    "                    else:\n",
    "                        p[x_root] = y_root\n",
    "                        s[y_root] += x_root\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if distance[x][y] >= k:\n",
    "                        for dx, dy in d[:2]:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < n > ny >= 0 and distance[nx][ny] >= k:\n",
    "                                union(nx * n + ny, x * n + y)\n",
    "                                # p[find(nx * n + ny)] = find(x * n + y)\n",
    "            return find(0) == find(n * n - 1)\n",
    "        left, right = 0, n << 1\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        inf = 1e9\n",
    "        safety = [[inf for i in range(n)] for j in range(n)]\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if(grid[i][j]==1):\n",
    "                    safety[i][j]=0\n",
    "                    q.append([i, j])\n",
    "        depth = 0\n",
    "        while len(q)>0:\n",
    "            l = len(q)\n",
    "            depth+=1\n",
    "            for _ in range(l):\n",
    "                i, j = q.popleft()\n",
    "                for i0, j0 in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                    if 0<=i+i0<n and 0<=j+j0<n and safety[i+i0][j+j0]==inf:\n",
    "                        safety[i+i0][j+j0] = depth\n",
    "                        q.append([i+i0, j+j0])\n",
    "        # for s in safety:\n",
    "        #     print(s)\n",
    "        # print()\n",
    "        # def bfs(flag, i, j, dir1, dir2, cur):\n",
    "        #     nonlocal n\n",
    "        #     if i==n or i==-1 or j==n or j==-1:\n",
    "        #         return 2*n\n",
    "        #     if flag[i][j]!=-1:\n",
    "        #         return flag[i][j]\n",
    "        #     if grid[i][j]==1:\n",
    "        #         return cur\n",
    "        #     ans = 2*n\n",
    "        #     for i0 in dir1:\n",
    "        #         ans = min(ans, bfs(flag, i+i0, j, [i0], dir2, cur+1))\n",
    "        #     for j0 in dir2:\n",
    "        #         ans = min(ans, bfs(flag, i, j+j0, dir1, [j0], cur+1))\n",
    "        #     flag[i][j]=ans\n",
    "        #     return ans\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         safety[i][j] = bfs([[-1]*n for i in range(n)], i, j, [1, -1], [1, -1], 0)\n",
    "        # dp = [n*n]+[0]*n\n",
    "        # for j in range(n):\n",
    "        #     for i in range(n):\n",
    "        #         dp[i+1] = min(max(dp[i], dp[i+1]), safety[j][i])\n",
    "        #     dp[0] = 0\n",
    "        #     print(dp)\n",
    "        def dfs(flag, i, j, tar):\n",
    "            if i==n or i==-1 or j==n or j==-1:\n",
    "                return False\n",
    "            if safety[i][j]<tar:\n",
    "                return False\n",
    "            if i==n-1 and j==n-1:\n",
    "                return True\n",
    "            if flag[i][j]:\n",
    "                return False\n",
    "            flag[i][j] = True\n",
    "            return dfs(flag, i-1, j, tar) or dfs(flag, i+1, j, tar) or dfs(flag, i, j-1, tar) or dfs(flag, i, j+1, tar)\n",
    "        l = 0\n",
    "        r = max([max(s) for s in safety])\n",
    "        ans = l\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if dfs([[False]*n for i in range(n)], 0, 0, m):\n",
    "                ans = max(ans, m)\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0]==1 or grid[-1][-1]==1:\n",
    "            return 0\n",
    "        risk = [[1e9]*n for _ in range(n)]\n",
    "        dirs = [[1,0], [0,1], [-1,0], [0,-1]]\n",
    "        q=[]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    q.append((i,j,0))\n",
    "                    risk[i][j] = 0\n",
    "                    \n",
    "        for i, j, dis in q:\n",
    "            for di, dj in dirs:\n",
    "                ii, jj = i+di, j+dj\n",
    "                if 0<=ii<n and 0<=jj<n and (dis+1)<risk[ii][jj]:\n",
    "                    q.append((ii, jj, dis+1))\n",
    "                    risk[ii][jj] = dis+1\n",
    "\n",
    "        def judge(r):\n",
    "            visited = [[0]*n for _ in range(n)]\n",
    "            def dfs(i, j):\n",
    "                if risk[i][j]<r:\n",
    "                    return\n",
    "                visited[i][j]=1\n",
    "                if visited[n-1][n-1]==1:\n",
    "                    return\n",
    "                for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                    if 0<=i+di<n and 0<=j+dj<n and visited[i+di][j+dj]==0:\n",
    "                        dfs(i+di, j+dj)\n",
    "            dfs(0,0)\n",
    "            return visited[-1][-1]\n",
    "        \n",
    "        left, right = 0, 2*n\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if judge(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        \n",
    "        return left-1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
